package sort;

import java.util.Arrays;

/*
    归并排序：
        把数组递归分为1/2，当分到元素为1个时，回溯合并
        关键在于merge方法
            每次都copy一个新数组，然后返回这个处理过的数组，覆盖原数组
            merge时分四种情况：
                左边已经扫完了
                右边已经扫完了
                都未扫完，但 array[leftIndex] <= array[rightIndex]
                都未扫完，但 array[leftIndex] > array[rightIndex]
 */
public class MergeSort {
    public static void main(String[] args) {
//        // 生成数组并打印
////        int[] array = Util.getRandomArray();
//        int[] array = new int[]{3, 2, 4, 7, 5, 5};
//        Util.printArrayFormat(array);
//
//        // 使用函数
//        array = mergeSort(array, 0, array.length - 1);
//
//        // 打印排序后的函数
//        Util.printArrayFormat(array);
//
//        // 判断是否排对了
//        System.out.println(Util.isSorted(array) ? "排对了" : "排错了");

        boolean isSorted = false;

        for (int i = 0; i < 10000; i++) {
            // 生成数组并打印
            int[] array = Util.getRandomArray();

            // 使用函数
            array = mergeSort(array, 0, array.length - 1);

            // 判断是否排对了
            isSorted = Util.isSorted(array);
            if (!isSorted) break;
        }

        System.out.println(isSorted ? "对了" : "错了");
    }

    public static int[] mergeSort(int[] array, int left, int right) {
        if (right - left <= 0) {
            return array;
        }

        int mid = left + (right - left) / 2;

        array = mergeSort(array, left, mid);
        array = mergeSort(array, mid + 1, right);

        array = merge(array, left, mid, mid + 1, right);

        return array;
    }

    private static int[] merge(int[] array, int left, int mid, int midPlus, int right) {
        int[] newArray = Arrays.copyOf(array, array.length);

        int leftIndex = left, rightIndex = midPlus, nowIndex = left;
        while (leftIndex <= mid || rightIndex <= right) {
            if (leftIndex > mid) {  // 如果左边已经走完了
                System.arraycopy(array, rightIndex, newArray, nowIndex, right - rightIndex + 1);
                break;
            }
            if (rightIndex > right) {
                System.arraycopy(array, leftIndex, newArray, nowIndex, mid - leftIndex + 1);
                break;
            }
            if (array[leftIndex] <= array[rightIndex]) {    // 如果左边小
                newArray[nowIndex++] = array[leftIndex++];
            } else {
                newArray[nowIndex++] = array[rightIndex++];
            }
        }
        return newArray;
    }
}
